package leetcode.D500.T402;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: DYZ
 * @Create: 2021-07-11 12:33:45 星期日
 */

public class Solution {
    public String removeKdigits(String num, int k) {
        Deque<Character> dq1 = new LinkedList<>();
        int count = 0;
        for(int i=0; i<num.length(); ++i) {
            char c = num.charAt(i);
            while(!dq1.isEmpty() && c < dq1.getFirst() && count < k) {
                count++;
                dq1.removeFirst();
            }
            if(c == '0' && dq1.isEmpty()) {
                continue;
            }
            dq1.addFirst(c);
        }
        while(count < k) {
            count++;
            if(!dq1.isEmpty()) {
                dq1.removeFirst();
            }
        }
        StringBuilder sb = new StringBuilder();
        while(!dq1.isEmpty()) {
            sb.append(dq1.getLast());
            dq1.removeLast();
        }
        return sb.length() > 0 ? sb.toString() : "0";
    }
}
